/**
 * Created by L.jp
 * Description:链接：https://www.nowcoder.com/questionTerminal/4af96fa010c44638a7e112abf65f7237?answerType=1&f=discussion
 * 来源：牛客网
 *
 * 给定一个长度为 n 的数组a，求它的最长严格上升子序列的长度。
 * 所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
 * 我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i和 j 满足 i<j 且 a[i]>=a[j]
 *  。
 * 数据范围：0<=n<=10^5,-10^9<=a[i]<=10^9
 * 要求：时间复杂度 O(nlogn) 空间复杂度 O(n)
 * User: 86189
 * Date: 2022-04-30
 * Time: 23:12
 */
public class Main {
    /*  注意时间复杂度是O（nlogn)，不能用我们之前的动态规划的方法求解，因为动态规划需要两层循环，时间复杂度是O（n^2)
        所以我们可以采用动态规划的方法+二分查找的方法
        使用动态规划，定义一个新的数组长度和原数组长度一样，新数组就存储着最长上升子序列，
        思想：
            新数组最后一个下标+1永远代表这个最长上升子序列的长度
        方法：
            遍历原数组，如果数组元素大于新数组的最后一个元素，说明可以加入自增序列，直接把这个元素加在新数组的最后面
            如果遍历到数组元素大于新数组最后一个元素，那么就用二分法在新数组中找到第一个比该元素大的下标，然后用该元素代替
            新数组的元素
            最后数组最后一个位置下标+1就是最长上升子序列
    *
    *
    * */
    public static int LIS (int[] a) {
        if(a.length==0){
            return 0;
        }
        //定义一个数组存储最长上升子序列
        int[] lis=new int[a.length];
        //定义一个下标遍历递增子序列数组
        int end=-1;
        for(int i = 0;i<a.length; i++){
            //如果是数组第一个元素或者原数组元素大于新数组的最后一个元素，那么它可以加入递增子序列数组
            if(i==0 || a[i] >lis[end]){
                //先把递增子序列的数组下标+1
                lis[++end]=a[i];
            }else{
                //使用二分法找到新数组中第一个比a[i]大的元素，然后替换它
                int index=binarySearch(lis,a[i],end);
                //可能会改变原数组元素的原来位置
                //但是end+1一直都是最长递增子序列的长度
                lis[index]=a[i];
            }
        }
        //返回长度
        return end+1;
    }
    public static  int binarySearch(int[] lis,int target,int end){
        int left=0;
        int right = end;
        while (left < right){
            int mid=(left+right)/2;
            if(lis[mid] < target){
                left=mid+1;
            }else{
                right = mid ;
            }
        }
        return left;
    }
    
    public static void main(String[] args) {
        int[] a={1,4,7,5,6};
        System.out.println(LIS(a));
    }
}
